package com.example.algorithm.recursion;


import java.util.ArrayList;
import java.util.List;

/**
 * 在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。
 * 一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。
 * 移动圆盘时受到以下限制:
 * (1) 每次只能移动一个盘子;
 * (2) 盘子只能从柱子顶端滑出移到下一根柱子;
 * (3) 盘子只能叠在比它大的盘子上。
 */
public class Hanota {
    public static void main(String[] args) {
        List<Integer> A = new ArrayList<>();
        A.add(4);
        A.add(3);
        A.add(2);
        A.add(1);

        List<Integer> B = new ArrayList<>();
        List<Integer> C = new ArrayList<>();
        System.out.println("移动之前C.size:" + C.size());
        hanota2(A, B, C);
        System.out.println("移动之后C.size:" + C.size());
        C.forEach(x -> {
            System.out.println(x);
        });

        // 为了打印递归移动顺序
        hanoi(4,'a', 'b','c');


    }

    /**
     * 递归模板
     * 递归，去的过程叫"递"，回来的过程叫"归"
     * 递是调用，归是结束后回来
     * 是一种循环，而且在循环中执行的就是调用自己
     * 三要素:
     *   结束条件
     *   函数主功能
     *   函数的等价关系式（参数、返回值、关系）
     * @return
     */
    public int recursion(int n) {
        // 递归结束条件
        if(n == 1) {
            return 1;
        }
        // 函数主体功能
        System.out.println(n);
        // .....

        // 递归调用自己,等价关系式f(n)=n+f(n-1) 转换为简单问题
        return n + recursion(n-1);

    }

    /**
     * 解法二:递归实现
     *
     * 1.递归结束条件:
     *   移动一个盘子
     *
     * 2.递归函数主功能:
     *   2.1 移动N-1个盘子到中间柱子
     *   2.2 移动第N个盘子到目标柱子
     *   2.3 将N-1个盘子从中间柱子移动到目标柱
     *
     * 3.函数的等价关系式
     *   3.1 参数:本轮盘子数量(n)、三个柱子（List）
     *   3.2 返回值:无返回值，因为list是传递的一个引用
     *   3.3 等价关系
     *       f(n, A, B, C)=f(n-1, A, C, B)+M(A, C)+f(n-1, B, A, C)
     *       将n个盘子从A移动到C拆解为
     *          将上面的n-1个盘子从A移动到B;
     *          将最下面的盘子从A移动到C;
     *          将n-1个盘子从B移动到C
     *
     * @param A
     * @param B
     * @param C
     */
    public static void hanota2(List<Integer> A, List<Integer> B, List<Integer> C) {
        movePlates(A.size(), A, B, C);
    }

    /**
     *
     * @param platesSize 要移动盘子的数量
     * @param A 从哪个盘子上移动
     * @param B 临时存放盘子
     * @param C 移动盘子到哪个柱子上
     */
    private static void movePlates(int platesSize, List<Integer> A, List<Integer> B, List<Integer> C) {
        if (platesSize == 1) {
            // 当只有一个盘子时，将该盘子从A柱子移动到C柱,然后返回
            C.add(A.remove(A.size() - 1));
            return;
        }

        // 将上面的n-1个盘子从A移动到B
        movePlates(platesSize - 1, A, C, B);
        // 将最下面的盘子从A移动到C
        C.add(A.remove(A.size()  - 1));
        // 将n-1个盘子从B移动到C
        movePlates(platesSize - 1, B, A, C);

    }

    /**
     * 从a移动到c，借助b。需要移动n个盘子
     * @param n
     * @param a
     * @param b
     * @param c
     */
    private static void hanoi(int n, char a, char b, char c) {
        if(n == 1){//递归重点，进行打印
            System.out.println(a+"->"+c);
            return;
        }
        hanoi(n-1,a,c,b);//递归移动
        hanoi(1,a,b,c);
        hanoi(n-1,b,a,c);
    }

    /**
     * 解法一:两步操作法
     * <p>
     * 1.将柱子摆成品字型，摆放顺序由圆盘数量奇偶性决定
     * 若n为奇数，按顺时针方向依次摆放A C B
     *   A
     * B   C
     * 若n为偶数，按顺时针方向依次摆放A B C
     *   A
     * C   B
     * 2.按下面规则移动盘子：
     *   2.1按顺时针方向把最小的盘子从当前的柱子移动到下一根柱子上
     *   2.2把另外两根柱子上可以移动的圆盘移动到新的柱子上
     *        把非空柱子上的圆盘移动到空柱子上
     *        当两根柱子都非空时，移动较小的圆盘
     * 循环2的操作，直到盘子全部到了C柱上为止
     * @param A
     * @param B
     * @param C
     */
    public static void hanota1(List<Integer> A, List<Integer> B, List<Integer> C) {
        int platesSize = A.size();
        List<Integer>[] threePillars = new List[3];
        // 1.根据盘子数量将柱子摆成“品”字型
        threePillars[0] = A;
        // 若n为奇数，按顺时针方向依次摆放A C B
        // 若n为偶数，按顺时针方向依次摆放A B C
        threePillars[1] = (platesSize % 2) == 0 ? B : C;
        threePillars[2] = (platesSize % 2) == 0 ? C : B;
        if ((platesSize % 2) == 0) {
            threePillars[1] = B;
            threePillars[2] = C;
            System.out.println("三个盘子顺时针摆放顺序: 0,1,2");
        } else {
            threePillars[1] = C;
            threePillars[2] = B;
            System.out.println("三个盘子顺时针摆放顺序: 0,2,1");
        }

        // 用于记录一轮移动中最小盘子所在的柱子下标，一轮结束后要++
        int curPillarIndex = 0;
        // 下一个柱子是:(curPillarIndex + 1) % 3
        int nextPillarIndex = 0;
        // 前一个柱子(下下个)是:(curPillarIndex + 2) % 3
        int prePillarInex = 0;
        int count = 1;
        while (C.size() < platesSize) {
            System.out.println("第" + count + "轮");
            // 编号最小盘子所在的柱子
            List<Integer> curPillar = threePillars[curPillarIndex];
            // 编号最小盘子所在柱子的下一个柱子
            List<Integer> nextPillar = threePillars[(curPillarIndex + 1) % 3];
            nextPillarIndex = (curPillarIndex + 1) % 3;
            // 编号最小盘子所在柱子的上一个柱子(最小盘子所在的下下个盘子)
            List<Integer> prePillar = threePillars[(curPillarIndex + 2) % 3];
            prePillarInex = (curPillarIndex + 2) % 3;
            // 2.1将最小的盘子移动到下一个柱子上
            System.out.println("将最小的" + curPillar.get(curPillar.size() - 1) +
                    "号盘子从" + curPillarIndex + "柱子,移动到" + nextPillarIndex + "号柱子上");
            nextPillar.add(curPillar.remove(curPillar.size() - 1));
            int preSize = prePillar.size();
            int curSize = curPillar.size();
            // 2.2把另外两根柱子上可以移动的圆盘移动到新的柱子上
               // 先分别获取pre和cur的最上面盘子编号，
               // 如果某个柱子为空，则将其置为最大值
            Integer prePillarTopPlate = (preSize == 0 ? Integer.MAX_VALUE : prePillar.get(prePillar.size() - 1));
            Integer curPillarTopPlate = (curSize == 0 ? Integer.MAX_VALUE : curPillar.get(curPillar.size() - 1));
              // 然后比较,将小的2盘子移动到另一个柱子上(因为当某个盘子为空时,一定是将另一盘子的最上层盘子移到该空柱子上)
            if (prePillarTopPlate < curPillarTopPlate) {
                System.out.println("将" + prePillar.get(preSize - 1) +
                        "号盘子从" + prePillarInex + "柱子,移动到" + curPillarIndex + "号柱子上");
                curPillar.add(prePillar.remove(preSize - 1));
            } else if (curPillarTopPlate < prePillarTopPlate) {
                System.out.println("将" + curPillar.get(curSize - 1) +
                        "号盘子从" + curPillarIndex + "柱子,移动到" + prePillarInex + "号柱子上");
                prePillar.add(curPillar.remove(curSize - 1));
            }
            count++;
            // 因为最小的盘子移动到了新盘子上所以索引要+1
            curPillarIndex = (curPillarIndex + 1) % 3;
            System.out.println("============================");
        }
    }

}
